package tree.StructureTreeNode;

import tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName BuildTreeII
 * @Description TODO
 * @Author lenovo
 * @Date 2023-03-28 11:01
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class BuildTreeII {


    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTreeNode(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTreeNode(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart >= preEnd || inStart >= inEnd) return null;
        Integer inNum = map.get(preorder[preStart]);
        Integer inLeft = inNum - inStart;

        TreeNode treeNode = new TreeNode(inorder[inNum]);
        //todo
        treeNode.left = buildTreeNode(preorder, preStart + 1, preStart + 1 + inLeft, inorder, inStart, inNum);
//        treeNode.right = buildTreeNode(preorder, preStart + 1 + inLeft, preEnd, inorder, inNum, )
        return treeNode;
    }

    public static void main(String[] args) {
        BuildTreeII buildTreeII = new BuildTreeII();
        System.out.println(buildTreeII.buildTree(new int[]{3, 9, 8, 5, 4, 10, 20, 15, 7}, new int[]{4, 5, 8, 10, 9, 3, 15, 20, 7}));
    }
}